#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution
{
  public:
    vector<int> solve(vector<int> &preOrder, vector<int> &inOrder)
    {
        // write code here
        int n = preOrder.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++)
        {
            mp[inOrder[i]] = i;
        }
        TreeNode *root = buildTree(preOrder, inOrder, 0, n - 1, 0, n - 1, mp);
        queue<TreeNode *> q;
        q.push(root);
        vector<int> res;
        while (!q.empty())
        {
            int lastVal = -1;
            int n = q.size();
            for (int i = 0; i < n; i++)
            {
                TreeNode *node = q.front();
                lastVal = node->val;
                q.pop();
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            res.push_back(lastVal);
        }
        return res;
    }

  private:
    // 递归构建二叉树
    TreeNode *buildTree(vector<int> &pre, vector<int> &vin, int preStart,
                        int preEnd, int vinStart, int vinEnd,
                        unordered_map<int, int> &indexMap)
    {
        // 递归终止条件：当前子树无节点
        if (preStart > preEnd)
            return nullptr;

        // 前序遍历的第一个元素为当前子树的根节点
        int rootVal = pre[preStart];
        TreeNode *root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int vinRootIndex = indexMap[rootVal];

        // 计算左子树节点数量
        int leftCount = vinRootIndex - vinStart;

        // 递归构建左子树
        root->left = buildTree(pre, vin, preStart + 1, preStart + leftCount,
                               vinStart, vinRootIndex - 1, indexMap);

        // 递归构建右子树
        root->right = buildTree(pre, vin, preStart + leftCount + 1, preEnd,
                                vinRootIndex + 1, vinEnd, indexMap);

        return root;
    }
};